package sort.cmp;

import sort.Sort;

/**
 * @Author: LDeng
 * @Date: 2021-03-24 13:03
 */
public class InsertionSort3<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            //将原来位置的元素插入到待插入索引的位置
            insert(begin,search(begin));
        }
    }

    //将source位置的元素插入到dest位置
    private void insert(int source,int dest){
        E e=array[source];
        for (int i = source; i >dest ; i--) {
            array[i]=array[i-1];
        }
        array[dest]=e;
    }

    // 传入没排序前的索引位置，
    // 已经排好序的数组区间范围是[0,index)
    // 利用二分搜索返回待插入元素的索引index
    private int search(int index){
        int begin=0;
        int end=index;
        while(begin<end){
            int mid=(begin+end)>>1;
            if(cmp(array[index],array[mid])<0){
                end=mid;
            }else {
                begin=mid+1;
            }
        }
        return begin;
    }
}

